package com.gitee.feizns.explore.data_structure.graph;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

/**
 * 1162. 地图分析
 * @author feizns
 * @since 2020/4/30
 */
public class MaxDistance {

    public static void main(String[] args) {
        System.out.println(new MaxDistance().maxDistance(new int[][]{
                {1, 0, 0, 1},
                {0, 0, 0, 0},
                {0, 0, 0, 0},
                {1, 0, 0, 1}
        }));
    }

    private int[][] grids;

    public int maxDistance(int[][] grids) {
        this.grids = grids;
        Queue<Integer> queue = new LinkedList<>();
        Set<Integer> visited = new HashSet<>();
        for (int i = 0; i < grids.length; i++) {
            for (int j = 0; j < grids.length; j++)
                if ( grids[i][j] == 1 ) {
                    int k = k(i, j);
                    queue.add(k);
                    visited.add(k);
                }
        }
        int dis = bfs(queue, visited);
        return dis > 0 ? dis : -1;
    }

    private int bfs(Queue<Integer> queue, Set<Integer> visited) {
        int dis = -1;
        while ( !queue.isEmpty() ) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                Integer cur = queue.remove();
                int x = x(cur);
                int y = y(cur);

                //top
                int k;
                if ( !visited.contains((k = k(x - 1, y))) && ocean(x - 1, y) ) {
                    queue.add(k);
                    visited.add(k);
                }

                //rig
                if ( !visited.contains((k = k(x, y + 1))) && ocean( x, y + 1 ) ) {
                    queue.add(k);
                    visited.add(k);
                }

                //btm
                if ( !visited.contains((k = k(x + 1, y))) && ocean(x + 1, y) ) {
                    queue.add(k);
                    visited.add(k);
                }

                //lef
                if ( !visited.contains((k = k(x, y - 1))) && ocean(x, y - 1) ) {
                    queue.add(k);
                    visited.add(k);
                }

            }
            dis++;
        }
        return dis;
    }

    private int x(int k) {
        return k / grids.length;
    }

    private int y(int k) {
        return k % grids.length;
    }

    private int k(int x, int y) {
        return x * grids.length + y;
    }

    private boolean ocean(int x, int y) {
        return (x >= 0 && x < grids.length && y >= 0 && y < grids.length) && grids[x][y] == 0;
    }

}
